package Hot100;

import javax.swing.text.Caret;

/**
 * @author zhangmin
 * @create 2021-12-22 14:20
 */
public class searchRange34 {

    /**
     * 34. 在排序数组中查找元素的第一个和最后一个位置
     * 给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。如果数组中不存在目标值 target，返回 [-1, -1]。
     * 左边界二分+右边界二分
     * */
    int boundSrarch(int[] nums,int target,boolean isLeft){
        int l=0,r=nums.length-1;
        while (l<=r){
            int mid=l+(r-l)/2;
            if (nums[mid]>target){
                //不返回，找左边界
                r=mid-1;
            }else if (nums[mid]<target){
                l=mid+1;
            }else if (nums[mid]==target){
                if (isLeft){
                    r=mid-1;
                }else {
                    l=mid+1;
                }
            }
        }
        if (isLeft){
            if (l>=nums.length||nums[l]!=target) return -1;
            return l;
        }else {
            if (r<0||nums[r]!=target) return -1;
            return r;
        }
    }
    public int[] searchRange(int[] nums, int target) {
        int l = boundSrarch(nums, target, true);
        int r = boundSrarch(nums, target, false);
        return new int[]{l,r};
    }
}
